package org.aplombh.java.awcing.basic.basics.sort.mergeSort;

public class MyMergeSort {


    /**
     * merge sort algorithm 归并排序
     *
     * @param ints  unsorted array 待排序数组
     * @param left  left margin 左边界
     * @param right right margin 右边界
     */
    public static void mergeSort(int[] ints, int left, int right) {

        // The temp arrays are used to store temporary data
        // tmp数组用来存储临时数组
        int[] tmp = new int[ints.length];

        // Running the unencapsulated method to sort ints array
        // 调用未包装的方法去排序数组

        unencapsulatedMergeSort(ints, tmp, 0, ints.length - 1);
    }

    /**
     * unencapsulated merge sort algorithm 未包装的归并排序算法
     *
     * @param ints  unsorted array 待排序数组
     * @param temp  cache array 缓存数组
     * @param left  left margin 左边界
     * @param right right margin 右边界
     */
    public static void unencapsulatedMergeSort(int[] ints, int[] temp, int left, int right) {


        // If the function reaches the boundary, the recursion exits
        // 如果方法到达边界，递归退出
        if (left >= right) return;


        // Recursive partition boundary;
        // 递归部分的边界
        int middle = left + right >> 1;


        // Merge sort left partition and right partition;
        // 左右两边递归排序
        unencapsulatedMergeSort(ints, temp, left, middle);
        unencapsulatedMergeSort(ints, temp, middle + 1, right);


        // k is the index of the Temp array
        // i is the starting index of the sorted left region
        // j is the starting index of the sorted right region
        // k是临时数组的下标
        // i是排好序的左部分起始下标
        // j是排好序的右部分起始下标
        int k = 0, i = left, j = middle + 1;

        // Merge the left and right regions
        // The temp arrays are used to store temporary data，
        // 归并左右两个部分
        // temp数组存储临时数据
        while (i <= middle && j <= right){
            if (ints[i] <= ints[j]) temp[k++] = ints[i++];
            else temp[k++] = ints[j++];
        }

        // If i less than or equal to middle,
        // it means that all the remaining numbers in the left region are greater than the  numbers in the right region,
        // and we add all the remaining numbers to the temp array;
        // 如果i<=middle，说明左边剩余部分所有数据都比右边部分的大，将所有剩余数据添加到temp数组中
        while (i <= middle)
            temp[k++] = ints[i++];


        // If j less than or equal to middle,
        // it means that all the remaining numbers in the left region are greater than the remaining numbers in the right region,
        // and we add all the remaining numbers to the temp array;
        // 如果j<=middle，说明左边剩余部分所有数据都比左边部分的大，将所有剩余数据添加到temp数组中
        while (j <= right)
            temp[k++] = ints[j++];


         // Store temporary data into ints array
        // 将temp数组数据回写到ints数组中
        for (i = left, j = 0; i <= right; i++, j++) ints[i] = temp[j];
    }
}
